难就难在如何满足它的空间和时间复杂度要求。
题目
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
思路
因为是求缺失的第一个正数,也就是说求从1开始缺失的最小的整数,对于一个长度为n的数组,缺失的正数只有这样两种可能:
1、缺失的正数是1到n中的某一个数,具体不知道
2、如果1到n都没有缺失的数,那么缺失的那个最小的数就默认是n+1
那么问题就被清晰处理了,题目要求遍历一次数组,只需要在遍历数组的时候顺便对一个1到n长度的标志数组进行mark,到时候找到第一个未被mark的标志位置,就是缺失的第一个正数,如果都mark了,那么缺失的就是n+1,这样就解决了时间复杂度的要求。
但是空间复杂度只能使用常数空间,如果要设定一个上述的长度为n的标志数组,那么使用的就是n级别的空间,不是常数空间,考虑使用传进来的nums数组,原理是这样的,设定约束条件,在nums中,尽量让最多的nums[i]=i+1,这样在nums中,每个数字,如果它是在1到n之间的数,那么它一定有一个属于它的位置(不重复的情况下,如果重复,那么就不用将它放到按约束条件应该放的位置,放在原位即可),将它调整到它应该处于的位置,调整结束之后。找到第一个不满足nums[i]=i+1的位置,那么它就是缺失的第一个正数,例子如下:
[1,1]
nums[0]=0+1
nums[1]!=1+1,按照约束条件,nums[1]的值是1,应该放在nums[0]上,但是nums[0]已经放了一个正确的数,所以保持原位
找到第一个不满足nums[i]=i+1条件的元素的索引为1,所以输出结果2.
[3,4,-1,1]
nums[0]!=0+1,按照约束条件,nums[0]=3,3应该放在nums[2]的位置上,交换两者的值,这里注意,被交换过来的值位置肯定是不对的,因为位置正确的值不会被交换,所以要再次进行约束条件判定,交换来的值是-1,所以不用管。
nums[1]!=1+1,按照约束条件,4应该放在nums[3]的位置上,交换两者位置,然后得到nums[1]等于1,也是错误的位置,然后寻找1应该处于的位置,发现nums[0]=-1,也是错误的,交换nums[0] and nums[1],交换来的值是-1,不再1到n之间,不管。
nums[2]位置正确
nums[3]位置正确
最后nums={1,-1,3,4},第一个不满足条件的就是nums[1],所以输出2.
[1,2,4,3]
nums[0]、nums[1]位置正确
nums[2]位置不对,交换到nums[3],交换来的3再进行判断,位置正确。
nums[3]位置正确
最后nums={1,2,3,4},数组内没有不满足的,所以返回n+1,返回5.
code
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;++i)
{
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1])//交换到满足条件的位置
//并且判断交换而来的数是否依然满足条件。
{
swap(nums[i], nums[nums[i] - 1]);
}
}
for(int i=0;i<n;++i)//找出第一个不满足条件的数
{
if(nums[i]!=i+1)
return i+1;
}
return n+1;//没有的情况下,输出n+1
}
};